#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef struct ListNode
{
	int val;
	struct ListNode* next;
}ListNode;

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
{
	ListNode* newHead = (ListNode*)malloc(sizeof(ListNode));
	ListNode* n1;
	ListNode* n2;
	ListNode* newTail=newHead;
	n1 = list1;
	n2 = list2;
	while (n1 && n2)
	{
		if (n1->val <= n2->val)
		{
			newTail->next = n1;
			newTail = newTail->next;
			n1 = n1->next;
		}
		else
		{
			newTail->next = n2;
			newTail = newTail->next;
			n2 = n2->next;
		}
		
	} 
	if (n1 == NULL && n2 != NULL)
	{
		newTail->next = n2;
	}
	else if (n2 == NULL && n1 != NULL)
	{
		newTail->next = n1;
	}
	return newHead->next;
}

void PrintList(ListNode* s)
{
	ListNode* pcur = s;
	while (pcur)
	{
		printf("%d->", pcur->val);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

int main()
{
	ListNode* a1 = (ListNode*)malloc(sizeof(ListNode*));
	ListNode* a2 = (ListNode*)malloc(sizeof(ListNode*));
	ListNode* a3 = (ListNode*)malloc(sizeof(ListNode*));
	ListNode* a4 = (ListNode*)malloc(sizeof(ListNode*));
	ListNode* a5 = (ListNode*)malloc(sizeof(ListNode*));

	a1->next = a2;
	a2->next = a3;
	a3->next = a4;
	a4->next = a5;
	a5->next = NULL;
	ListNode* pa = a1;

	a1->val = 1;
	a2->val = 2;
	a3->val = 3;
	a4->val = 4;
	a5->val = 5;

	ListNode* b1 = (ListNode*)malloc(sizeof(ListNode*));
	ListNode* b2 = (ListNode*)malloc(sizeof(ListNode*));
	ListNode* b3 = (ListNode*)malloc(sizeof(ListNode*));
	ListNode* b4 = (ListNode*)malloc(sizeof(ListNode*));
	ListNode* b5 = (ListNode*)malloc(sizeof(ListNode*));

	b1->next = b2;
	b2->next = b3;
	b3->next = b4;
	b4->next = b5;
	b5->next = NULL;
	ListNode* pb = b1;

	b1->val = 11;
	b2->val = 12;
	b3->val = 13;
	b4->val = 14;
	b5->val = 15;

	PrintList(a1);
	PrintList(b1);

	ListNode*L= mergeTwoLists(a1, b1);

	PrintList(L);

	return 0;
}